/*
指导逻辑：
1.逐层向下
2.先排序后比较
3.先对对像进行键排序，后对数组进行排序。

用法：
json = sortObjectOrArray(json)
if(sortAndCompare(obj1, obj2) > 0){
  xxx
}
if(isEqual(obj1, obj2){
  xxx
}
*/

function isObject(obj){
  return obj != null && !(obj instanceof Array) && (typeof obj) == 'object'
}

function isArray(obj){
  return obj != null && obj instanceof Array
}

/**
 * 对对像按键序排列
 * 
 * @param {*} obj object或者array对像
 * @param {*} parentObjArr 不包含自身的上级清单，避免无限递归，可为空
 * @returns 排序后的对像，非object非array的对像直接返回原对像
 */
function sortObjectDeep(obj, parentObjArr){
  if(isObject(obj)){
    if(!parentObjArr){
      parentObjArr = []
    }
    let ks = Object.keys(obj)
    //按键值自然顺序排列
    ks.sort()
    for (let i = 0; i < ks.length; i++) {
      const k = ks[i];
      let tmpObj = obj[k];
      delete obj[k]
      if((isArray(tmpObj) || isObject(tmpObj)) && !inArray(tmpObj, parentObjArr)){
        tmpObj = sortObjectDeep(tmpObj, [...parentObjArr, obj])
      }
      obj[k] = tmpObj
    }
  }else if(isArray(obj)){
    for (let i = 0; i < obj.length; i++) {
      let o = obj[i];
      if((isArray(o) || isObject(o)) && !inArray(o, parentObjArr)){
        o = sortObjectDeep(o, [...parentObjArr, obj])
      }
      obj[i] = o
    }
  }
  // 不符合情况时直接返回
  return obj
}

/**
 * 对数组进行深度排序（比较内容进行冒泡排序）
 * 
 * @param {*} objOrArr object或者array对像
 * @param {*} parentObjArr 不包含自身的上级清单，避免无限递归，可为空
 * @returns 排序后的对像，非object非array的对像直接返回原对像
 */
function sortArrayDeep(objOrArr, parentObjArr, sortedArray){
  if(isArray(objOrArr) && !inArray(objOrArr, sortedArray)){
    if(!parentObjArr){
      parentObjArr = []
    }
    if(!sortedArray){
      sortedArray = []
    }
    if(objOrArr != null && objOrArr.length > 0){
      // 冒泡排序。要在排序交换的的时候进行数据处理
      var len = objOrArr.length;
      for (var i = 0; i < len - 1; i++) { // 执行n-1轮比较
        for (var j = 0; j < len - i - 1; j++) { // 每一轮比较的次数递减
          var temp1 = objOrArr[j];
          var temp2 = objOrArr[j + 1];
          var parentObjArrSub = [...parentObjArr, objOrArr];
          temp1 = sortArrayDeep(temp1, parentObjArrSub, sortedArray);
          temp2 = sortArrayDeep(temp2, parentObjArrSub, sortedArray);
          var result = compareObject(temp1, temp2, parentObjArrSub, parentObjArrSub);
          if (result > 0) { // 如果当前元素大于下一个元素，交换它们的位置 objOrArr[j] > objOrArr[j + 1]
            objOrArr[j] = temp2;
            objOrArr[j + 1] = temp1;
          }
        }
      }
    }
    sortedArray.push(objOrArr)
    return objOrArr
  }else {
    // 不匹配的直接返回
    return objOrArr
  }
}

/**
 * 判断对象是否在数组里面或和当前对像相同
 * @param {*} arr 数组列表
 * @param {*} obj 对像
 * @param {*} selfObject 当前对像，可为空（不判断）
 * @returns true在，否则false
 */
function inArray(arr , obj, selfObject){
  if(arr != null && arr.length > 0 && obj != null){
    for (let i = 0; i < arr.length; i++) {
      if(obj === arr[i]){
        return true
      }
    }
  }
  return selfObject != null && selfObject === obj
}

/**
 * 比较两个对象（本函数不进行任何排序，只是进行深度比较），所以请先调用进行排序后再调用本函数。
 * 然后进行比较。
 * @param {*} obj1 前者（已进行深度排序的对像）
 * @param {*} obj2 后者（已进行深度排序的对像）
 * @param {*} parentObjArr1 不包含obj1自身的上级清单，避免无限递归，可为空
 * @param {*} parentObjArr2 不包含obj2自身的上级清单，避免无限递归，可为空
 * @returns 比较结果信息:相同返回0,前者大返回1,后者大返回-1。
 */
function compareObject(obj1, obj2, parentObjArr1, parentObjArr2) {
  if(!parentObjArr1){
    parentObjArr1 = [obj1]
  }
  if(!parentObjArr2){
    parentObjArr2 = [obj2]
  }
  //2个为空
  if (obj1 == null && obj2 == null) {
    return 0
  }
  //其中1个为空
  if (obj1 == null || obj2 == null) {
    if (obj1 != null) {
      return 1
    }
    if (obj2 != null) {
      return -1
    }
  }
  let t1 = typeof obj1;
  let t2 = typeof obj2;
  //类型不同
  if(t1 != t2){
    if(t1 > t2){
      return 1
    }
    if(t2 > t1){
      return -1
    }
  }
  //完全相同
  if(obj1 == obj2){
    return 0
  }
  if(t1 == 'object' && t2 !='object'){
    return 1
  }
  if(t1 != 'object' && t2 =='object'){
    return -1
  }
  if(t1 == 'object' && t2 =='object'){
    // 对像类型
    if(!isArray(obj1) && isArray(obj2)){
      return -1
    }
    if(isArray(obj1) && !isArray(obj2)){
      return 1
    }
    if(isArray(obj1) && isArray(obj2)){
      //数组
      let arr1 = obj1
      let arr2 = obj2
      if(arr1.length != arr2.length){
        let dif = (arr1.length - arr2.length) > 0 ? 1 : -1;
        return dif
      }
      for (let j = 0; j < arr1.length; j++) {
        const o1 = arr1[j];
        const o2 = arr2[j];
        //是否在上级对象里。引用上级对象导致死循环，需要避免死循环
        let in1 = inArray(parentObjArr1, o1, arr1)
        let in2 = inArray(parentObjArr2, o2, arr2)
        if(in1 || in2){
          //1不在2在
          if(!in1){
            return 1
          }
          //1在2不在
          if(!in2){
            return -1
          }
          //两个都在
          if(in1 && in2){
            return 0
          }
        }
        //两个都不在，开始递归比较
        let parentObjArr1sub = [...parentObjArr1, arr1, o1]
        let parentObjArr2sub = [...parentObjArr2, arr2, o2]
        let result = compareObject(o1, o2, parentObjArr1sub, parentObjArr2sub)
        if(result != 0){
          return result
        }
      }
      return 0
    }else{
      //对象
      let parentObjArr1sub = [...parentObjArr1, obj1]
      let parentObjArr2sub = [...parentObjArr2, obj2]
      let newObj1 = obj1
      let newObj2 = obj2
      let ks1 = Object.keys(newObj1)
      let ks2 = Object.keys(newObj2)
      if(ks2.length != ks1.length){
        let dif = (ks1.length - ks2.length) > 0 ? 1 : -1;
        return dif
      }
      ks1.sort()
      ks2.sort()
      for (let i = 0; i < ks1.length; i++) {
        let k1 = ks1[i]
        let k2 = ks2[i]
        if(k1 != k2){
          let dif = (k1 > k2) ? 1 : -1
          return dif
        }
      }
      let parentObjs = []
      parentObjs.push()
      for (let i = 0; i < ks1.length; i++) {
        let k1 = ks1[i]
        let k2 = ks2[i]
        const o1 = newObj1[k1];
        const o2 = newObj2[k2];
        //是否在上级对象里（可会导致死循环）
        let in1 = inArray(parentObjArr1, newObj1, o1)
        let in2 = inArray(parentObjArr2, newObj2, o2)
        if(in1 || in2){
          //1不在2在
          if(!in1){
            return 1
          }
          //1在2不在
          if(!in2){
            return -1
          }
          //两个都在
          if(in1 && in2){
            return 0
          }
        }
        //两个都不在，开始递归比较
        let result = compareObject(o1, o2, parentObjArr1sub, parentObjArr2sub)
        if(result != 0){
          return result
        }
      }
      return 0
    }
  }else{
    //基本类型
    if(obj1 > obj2){
      //1大
      return 1
    }else if(obj1 < obj2){
      //2大
      return -1
    }else{
      return 0
    }
  }
}

/**
 * 对数组或对象进行排序（对像按键序排列，数组则比较内容进行排序），该函数不应该被以递归的方式使用。
 * @param {*} objOrArr object或者array对像
 * @returns 排序后的对像，非object非array的对像直接返回原对像
 */
export function sortObjectOrArray(objOrArr){
  objOrArr = sortObjectDeep(objOrArr, [])
  objOrArr = sortArrayDeep(objOrArr, [], [])
  return objOrArr
}

/**
 * 比较两个对象（先排序后比较），该函数不应该被以递归的方式使用。
 * 代码逻辑：先调用sortObjectOrArray进行排序，然后进行比较。相同返回0,前者大返回1,后者大返回-1。
 * @param {*} obj1 前者
 * @param {*} obj2 后者
 * @returns 比较结果信息:相同返回0,前者大返回1,后者大返回-1。
 */
export function sortAndCompare(obj1, obj2) {
  // 先排序
  let o1 = sortObjectDeep(obj1, [])
  let o2 = sortArrayDeep(obj2, [], [])
  // 后比较
  return compareObject(o1, o2, parentObjArr1sub, parentObjArr2sub)
}

/**
 * 比较两个对像（支持对像或数组、嵌套对像或数组）是否内容相同（顺序无关）
 * @param {*} obj1 前者
 * @param {*} obj2 后者
 * @returns 
 */
export function isEqual(obj1, obj2){
  return sortAndCompare(obj1, obj2) == 0
}
